#include <bits/stdc++.h>

#include "tree.h"
using namespace std;
class Solution {
 private:
  vector<vector<int>> res;
  void dfs(TreeNode* root, vector<int>& path, int target) {
    if (root == nullptr) {
      return;
    }
    path.push_back(root->val);  //添加结点
    target -= root->val;        //更新target

    if (root->left == nullptr && root->right == nullptr && target == 0) {
      //如果已经到达了根结点，并且路径和已经满足要求
      res.emplace_back(path);
    }

    vector<int> left_path = path;
    dfs(root->left, left_path, target);

    vector<int> right_path = path;
    dfs(root->right, right_path, target);
  }

 public:
  vector<vector<int>> pathSum(TreeNode* root, int target) {
    if (root == nullptr) {
      return {};
    }

    vector<int> path;
    dfs(root, path, target);

    return res;
  }
};